package com.sheepone.util.algorithm;

import java.util.Arrays;

/**
 * @author Miss.杨
 * @description <p>
 * @since 2024/2/24 - 14:48
 */
public class KmpUtil {

    /**
     * 给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。
     * 单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。
     * 如果 word 不是 sequence 的子串，那么重复值 k 为 0 。
     *
     * 例如：
     * sequence = "aaabaaaabaaabaaaabaaaabaaaabaaaaba"
     * word = "aaaba"
     * k = 5;
     * @param sequence
     * @param word
     * @return 最大连续重复值
     */
    public static int maxConsecutiveRepeatValue(String sequence, String word) {
        int n = sequence.length();
        int m = word.length();
        if (n < m) {
            return 0;
        }
        int[] next = PrefixAndSuffixUtil.longestCommonPrefixAndSuffixLengthArray(word);
        int[] dp = new int[n];
        int i = 0, j = 0;
        while (i < n) {
            if (sequence.charAt(i) == word.charAt(j)) {
                if (++j == m) {
                    // 注意这里不能直接赋值为0
                    j = next[j - 1];
                    dp[i] = (i >= m ? dp[i - m] : 0) + 1;
                }
                i++;
            } else {
                if (j == 0) {
                    i++;
                } else {
                    j = next[j - 1];
                }
            }
        }

        return Arrays.stream(dp).max().getAsInt();
    }


}
